package com.lfg.leetcode.leetcode0;

import java.util.HashSet;
import java.util.Set;

public class No87isScramble {

    public static void main(String[] args) {
        boolean ret = isScramble("ccabcbabcbabbbbcbb", "bbbbabccccbbbabcba");
        System.out.println("[" + ret + "]");
    }

    public static boolean isScramble(String s1, String s2) {
        if (null == s1 || s2 == null) {
            return s2 == null;
        }
        if ("".equals(s1) || "".equals(s2)) {
            return s1.equals(s2);
        }
        if (s1.equals(s2)) {
            return true;
        }
        if (checkElement(s1, s2, s1.length(), s2.length())) return false;
        return checkScramble(s1, s2);
//        return checkScramble(s1, 0, s1.length() - 1, s2, 0, s2.length() - 1);
    }


    public static boolean checkScramble(String s1, String s2) {
        int length1 = s1.length();
        int length2 = s2.length();
        if (length1 != length2) {
            return false;
        }
        if (length1 == 1) {
            return s1.equals(s2);
        }
        if (s1.equals(s2)) {
            return true;
        }


        if (checkElement(s1, s2, length1, length2)) return false;

        for (int i = 1; i < length1; i++) {
            String s11 = s1.substring(0, i);
            String s12 = s1.substring(i);
            String s21 = s2.substring(0, i);
            String s22 = s2.substring(i);
            if (isScramble(s11, s21) && isScramble(s12, s22)) return true;
            s21 = s2.substring(s1.length() - i);
            s22 = s2.substring(0, s1.length() - i);
            if (isScramble(s11, s21) && isScramble(s12, s22)) return true;
        }
        return false;
    }

    private static boolean checkElement(String s1, String s2, int length1, int length2) {
        Set<Character> set = new HashSet<Character>(length1);
        for (int i = 0; i < length1; i++) {
            set.add(s1.charAt(i));
        }
        for (int i = 0; i < length2; i++) {
            if (!set.contains(s2.charAt(i))) {
                return true;
            }
        }
        return false;
    }


    public static boolean isScramble2(String s1, int startIndex1, int endIndex1, String s2, int startIndex2, int endIndex2) {
        if (endIndex1 < startIndex1) {
            return false;
        }
        if (endIndex1 - startIndex1 != endIndex2 - startIndex2) {
            return false;
        }
        if (endIndex2 >= s2.length() || endIndex1 >= s1.length() || startIndex1 < 0 || startIndex2 < 0) {
            return false;
        }
        if (endIndex1 == startIndex1) {
            return s1.charAt(startIndex1) == s2.charAt(startIndex2);
        }
        int length = endIndex2 - startIndex2;
        Set<Character> set = new HashSet<Character>(length + 1);
        for (int i = startIndex1; i < endIndex1; i++) {
            set.add(s1.charAt(i));
        }
        for (int i = startIndex2; i < endIndex2; i++) {
            if (!set.contains(s2.charAt(i))) {
                return false;
            }
        }

        for (int i = 0; i < length; i++) {
            if (isScramble2(s1, startIndex1, startIndex1 + i, s2, startIndex2, startIndex2 + i)
                    && isScramble2(s1, startIndex1 + i + 1, endIndex1, s2, startIndex2 + i + 1, endIndex2)) {
                return true;
            }
            if (isScramble2(s1, startIndex1, startIndex1 + i, s2, endIndex2 - i, endIndex2)
                    && isScramble2(s1, startIndex1 + i + 1, endIndex1, s2, startIndex2, endIndex2 - i - 1)) {
                return true;
            }
        }
        return false;
    }

}

